#include "resolvedor.h"

Resolvedor::Resolvedor(){

}


//Resuelve usando programacion dinamica, basicamente lo que hace es calcula cual es la
//minima distancia (usando dijkstra y las prioridades) desde el nodo actual hacia el siguiente, y actualiza el camino,
//despues desde ese siguiente nodo realiza el mismo procedimiento
//Ahi te dejo un Pseudocodigo:
/*
 Resolver:
 * NodosSinContemplar=Todos los nodos menos Inicio;
 * nodoActual = Inicio;
 * while(NodosSinContemplar no sea vacio){
 *      Distancias,Padres = Dijkstra(dist_orig, inicio);
 *      mejorNodo = Al nodo sin contemplar en donde la distancia calculada con dijkstra menos su prioridad sea la menor de todas
 *      NodosSinContemplar.erase(mejorNodo);
 *      Agrego el camino desde el nodo actual al mejor nodo a la lista resultado
 *      nodoActual=MejorNodo;
 * }
 * return result
*/
list<int> Resolvedor::resolverProgDinamica(float** dist_orig, float * prioridades, int inicio, int nodos){
    list<int> result;

    result.push_back(inicio);

    list<int> nodosSinContemplar;
    for(int i=0;i<nodos;i++){
        if(i!=inicio){
            nodosSinContemplar.push_back(i);
        }
    }

    int nodoActual = inicio;

    while(!nodosSinContemplar.empty()){
        float * distancias = new float[nodos];
        int * padres = new int[nodos];
        this->dijkstra(dist_orig,padres,distancias,nodos,nodoActual);

        list<int>::iterator it = nodosSinContemplar.begin();
        int mejor_nodo = (*it);
        float mejor_costo = distancias[*it] / prioridades[*it];
        list<int>::iterator mejor_puntero = it;
        it++;
        while(it!=nodosSinContemplar.end()){
            if(distancias[*it] / prioridades[*it] < mejor_costo){
                mejor_nodo = (*it);
                mejor_costo = distancias[*it] / prioridades[*it];
                mejor_puntero = it;
            }
            it++;
        }

        nodosSinContemplar.erase(mejor_puntero);
        int i=mejor_nodo;
        list<int> camino;
        camino.push_front(mejor_nodo);
        while(padres[i]!=-1){
            camino.push_front(padres[i]);
            i=padres[i];
        }

        for(list<int>::iterator it2=camino.begin();it2!=camino.end();it2++){
            result.push_back(*it2);
        }

        nodoActual = mejor_nodo;
    }
    return result;
}


//Algoritmo de dijkstra(calcula dado un grafo no conexo y un nodo, calcula las distancias minimas desde ese nodo hacia el resto, y los caminos para llegar a los mismos)
void Resolvedor::dijkstra(float ** distancias_orig, int * padres, float * result, const int nodos, const int inicio){
    float ** distancias=new float*[nodos];
    list<arco> arcos;
    bool visitados[nodos];
    
    for(int i=0;i<nodos;i++){
        distancias[i]= new float[nodos];
        for(int j=0;j<nodos;j++){
            if (distancias_orig[i][j] == __INF__){
                distancias[i][j] = 9999;
            } else {
                distancias[i][j] = distancias_orig[i][j];
            }
        }
    }

    for (int i=0;i<nodos;i++){
        visitados[i]=false;
        padres[i]=-1;

        result[i]=distancias[inicio][i];

        if (distancias[inicio][i]!=__INF__ && i != inicio){
            arco nuevo;
            nuevo.costo = distancias[inicio][i];
            nuevo.destino = i;
            arcos.push_front(nuevo);
        }
    }

    visitados[inicio] = true;

    for(int i=0;i<nodos;i++){
        int min_nodo;
        int min_costo=9999;

        list<arco>::iterator min_it;

        for(list<arco>::iterator it=arcos.begin();it!=arcos.end();it++){
            if(min_costo > it->costo && !visitados[it->destino]){
                min_nodo = it->destino;
                min_costo = it->costo;
                min_it = it;
            }
        }

        if(min_costo < 9999){
            arcos.erase(min_it);

            visitados[min_nodo]=true;

            for(int j=0;j<nodos;j++){
                if(!visitados[j]){
                    float distancia_actual=distancias[inicio][j];
                    float distancia_mejorada=distancias[inicio][min_nodo] + distancias[min_nodo][j];

                    if(distancia_actual > distancia_mejorada){
                        distancias[inicio][j] = distancia_mejorada;
                        result[j]=distancia_mejorada;
                        padres[j]=min_nodo;

                        arco nuevo;
                        nuevo.costo = distancias[inicio][j];
                        nuevo.destino = j;
                        arcos.push_front(nuevo);
                    }
                }
            }
        }
    }
}
